package demo.practice.linklist;

import demo.practice.ListNode;

public class P160 {

    /**
     * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
     * 输出：Reference of the node with value = 8
     * 输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
     * 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
     * 相交链表
     */

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //思路，
        // 1、判断终结点是否相同，相同则相交
        // 2、分别求出长度
        // 3长的节点先走  多出来的长度次，然后再双指针一起走，然后对比当前节点是否相同。
        //其中1、2可以一次性做完

        int lena=0;//计数a的长度
        ListNode current=headA;
        while (current.next!=null){
            current=current.next;
            lena++;
        }
        ListNode tailA=current;


        int lenb=0;//计数b的长度
        current=headB;
        while (current.next!=null){
            current=current.next;
            lenb++;
        }
        if(tailA!=current)
            return null;

        current=headA;
        ListNode currentb=headB;

        if(lena>lenb){
            int time=0;
            while (time<lena-lenb){
                current=current.next;
                time++;
            }
        }else if(lena<lenb) {
            int time=0;
            while (time<lenb-lena){
                currentb=currentb.next;
                time++;
            }
        }


        while (current.next!=null){
            if(current==currentb)
                return current;
            current=current.next;
            currentb=currentb.next;
        }

        return current==currentb? current:null;

    }


}
